#include <iostream>
#include <string>
#ifndef BINARYTREE
#define BINARYTREE
template<typename TValue>
class BinaryTree
{
public:
	enum class ChildSide { Left, Right, };
	using Side = ChildSide;
	using ValueType = TValue;
private:
	BinaryTree* pLeft;
	BinaryTree* pRight;
	BinaryTree* pBase;
	Side side;// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义；不应由自己修改，而应由双亲修改
	int count;
public:
	TValue Value;
public:
	// 构造只有一个节点的树，并且元素为默认值
	BinaryTree();
	// 用指定值构造只有一个节点的树
	BinaryTree(const TValue& value);
	// 构造一个树，根节点的元素为指定值，并指定一个子树
	BinaryTree(const TValue& value, BinaryTree* pChild, Side side);
	// 构造一个树，根节点的元素为指定值，并指定左右两个子树
	BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild);
	// 析构该树及其所有子树
	~BinaryTree();
	BinaryTree(const BinaryTree&) = delete;
	// 接管一个树，被接管的树成为一个孤立的节点
	BinaryTree(BinaryTree&& other);
	// 获取该树的双亲的指针
	BinaryTree* Parent();
	// 获取左子树的指针
	BinaryTree* LeftChild();
	// 获取右子树的指针
	BinaryTree* RightChild();
	// 获取节点总数
	int Count();
	// 获取树到最叶子节点的最大深度
	int DepthToLeaf();
	// 获取树到根节点的最大深度
	int DepthFromRoot();
	// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义
	Side SideOfParent();
	// 设置指定子树，先前的子树会被析构
	void SetChild(BinaryTree* pChild, Side side);
	// 删除指定子树，将其析构
	void RemoveChild(Side side);
	// 移除指定子树，但不会析构该子树，而是返回指向它的指针
	BinaryTree* ReleaseChild(Side side);
	BinaryTree* ReleaseChild(BinaryTree* pChild);
};

template<typename TValue>
BinaryTree<TValue>::BinaryTree()
{
	this->pLeft = nullptr;
	this->pRight = nullptr;
	this->pBase = nullptr;
	this->count = 1;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value)
{
	this->pLeft = nullptr;
	this->pRight = nullptr;
	this->pBase = nullptr;
	this->Value = value;
	this->count = 1;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pChild, Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		this->pLeft = pChild;
		pChild->side = Side::Left;
		this->pRight = nullptr;
		break;
	}
	case Side::Right:
	{
		this->pRight = pChild;
		pChild->side = Side::Right;
		this->pLeft = nullptr;
		break;
	}
	default:
		break;
	}
	pChild->pBase = this;
	this->Value = value;
	this->count = 1 + pChild->count;
	this->pBase = nullptr;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild)
{
	this->pLeft = pLChild;
	pLChild->side = Side::Left;
	this->pRight = pRChild;
	pRChild->side = Side::Right;
	this->pBase = nullptr;
	pLChild->pBase = this;
	pRChild->pBase = this;
	this->Value = value;
	this->count = 1 + pLChild->count + pRChild->count;
}

template<typename TValue>
BinaryTree<TValue>::~BinaryTree()
{
	delete this->pLeft;
	delete this->pRight;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(BinaryTree&& other)
{
	this->pBase = other.pBase;
	this->pLeft = other.pLeft;
	this->pRight = other.pRight;
	this->count = other.count;
	this->side = other.side;
	this->Value = other.Value;
	if (this->pLeft != nullptr)
	{
		this->pLeft->pBase = this;
	}
	if (this->pRight != nullptr)
	{
		this->pRight->pBase = this;
	}
	if (this->pBase != nullptr)
	{
		switch (this->side)
		{
		case Side::Left:
		{
			this->pBase->pLeft = this;
			break;
		}
		case Side::Right:
		{
			this->pBase->pRight = this;
			break;
		}
		default:
			break;
		}
	}
	other.pBase = nullptr;
	other.pLeft = nullptr;
	other.pRight = nullptr;
	other.count = 1;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::Parent()
{
	return this->pBase;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::LeftChild()
{
	return this->pLeft;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::RightChild()
{
	return this->pRight;
}

template<typename TValue>
int BinaryTree<TValue>::Count()
{
	return this->count;
}

template<typename TValue>
int BinaryTree<TValue>::DepthToLeaf()
{
	int leftDepth = 0, rightDepth = 0;
	if (this->LeftChild() != nullptr)
	{
		leftDepth = this->LeftChild()->DepthToLeaf();
	}
	if (this->RightChild() != nullptr)
	{
		rightDepth = this->RightChild()->DepthToLeaf();
	}
	if (leftDepth >= rightDepth)
	{
		return leftDepth + 1;
	}
	else
	{
		return rightDepth + 1;
	}
}

template<typename TValue>
int BinaryTree<TValue>::DepthFromRoot()
{
	int depth = 0;
	BinaryTree<TValue>* pTree = this;
	while (pTree->pBase != nullptr)
	{
		++depth;
		pTree = pTree->pBase;
	}
	return depth;
}

template<typename TValue>
typename BinaryTree<TValue>::Side BinaryTree<TValue>::SideOfParent()
{
	return this->side;
}

template<typename TValue>
void BinaryTree<TValue>::SetChild(BinaryTree* pChild, Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			delete this->pLeft;
			this->pLeft = nullptr;
		}
		if (pChild != nullptr)
		{
			this->pLeft = pChild;
			pChild->pBase = this;
			pChild->side = Side::Left;
			this->count += pChild->count;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			delete this->pRight;
			this->pRight = nullptr;
		}
		if (pChild != nullptr)
		{
			this->pRight = pChild;
			pChild->pBase = this;
			pChild->side = Side::Right;
			this->count += pChild->count;
		}
		break;
	}
	default:
		break;
	}
}

template<typename TValue>
void BinaryTree<TValue>::RemoveChild(Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			delete this->pLeft;
			this->pLeft = nullptr;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			delete this->pRight;
			this->pRight = nullptr;
		}
		break;
	}
	default:
		break;
	}
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(Side side)
{
	BinaryTree* pTree = nullptr;
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			pTree = this->pLeft;
			this->pLeft = nullptr;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			pTree = this->pRight;
			this->pRight = nullptr;
		}
		break;
	}
	default:
		break;
	}
	if (pTree != nullptr)
	{
		pTree->pBase = nullptr;
	}
	return pTree;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(BinaryTree* pChild)
{
	if (pChild == nullptr)
	{
		return nullptr;
	}
	if (pChild->pBase != this)
	{
		return nullptr;
	}
	return this->ReleaseChild(pChild->side);
}

#endif // !BINARYTREE


using Tree = BinaryTree<char>;

class InThre_adedTree
{
public:
	enum class PointerType
	{
		 Link, Thre_ad,
	};

private:
	InThre_adedTree* pLeft;
	InThre_adedTree* pRight;
	PointerType leftTag;
	PointerType rightTag;
	char value;
public:
	// 构造单个节点的树
	InThre_adedTree()
	{
		this->pLeft = this->pRight = nullptr;
		this->leftTag = this->rightTag = PointerType::Thre_ad;
		this->value = '\0';
	}

	InThre_adedTree(char value)
	{
		this->pLeft = this->pRight = nullptr;
		this->leftTag = this->rightTag = PointerType::Thre_ad;
		this->value = value;
	}

	// 析构树及其子树
	~InThre_adedTree()
	{
		if (this->leftTag == PointerType::Link)
		{
			delete this->pLeft;
		}
		if (this->rightTag == PointerType::Link)
		{
			delete this->pRight;
		}
	}

	// 复制一个树并线索化
	void CopyTree(Tree& tree)
	{
		this->Copy(&tree);
		InThre_adedTree* tempHead = new InThre_adedTree('*');
		tempHead->leftTag = PointerType::Link;
		tempHead->rightTag = PointerType::Thre_ad;
		tempHead->pLeft = this;
		tempHead->pRight = tempHead;
		InThre_adedTree* pre = tempHead;
		this->Thre_ading(pre);
		tempHead->pRight->pLeft = nullptr;
		tempHead->pLeft = nullptr;
		delete tempHead;
	}

	InThre_adedTree* Precursor()
	{
		if (this->leftTag == PointerType::Thre_ad)
		{
			return this->pLeft;
		}
		else
		{
			auto p = this->pLeft;
			while (p->rightTag == InThre_adedTree::PointerType::Link)
			{
				p = p->pRight;
			}
			return p;
		}
	}

	InThre_adedTree* Successor()
	{
		if (this->rightTag == PointerType::Thre_ad)
		{
			return this->pRight;
		}
		else
		{
			auto p = this->pRight;
			while (p->leftTag == InThre_adedTree::PointerType::Link)
			{
				p = p->pLeft;
			}
			return p;
		}
	}

	InThre_adedTree* Right()
	{
		return this->pRight;
	}

	InThre_adedTree* Left()
	{
		return this->pLeft;
	}

	PointerType RightTag()
	{
		return this->rightTag;
	}

	PointerType LeftTag()
	{
		return this->leftTag;
	}

	char& Value()
	{
		return this->value;
	}
private:
	void Copy(Tree* tree)
	{
		this->value = tree->Value;
		if (tree->LeftChild() != nullptr)
		{
			this->pLeft = new InThre_adedTree();
			this->leftTag = PointerType::Link;
			this->pLeft->Copy(tree->LeftChild());
		}
		if (tree->RightChild() != nullptr)
		{
			this->pRight = new InThre_adedTree();
			this->rightTag = PointerType::Link;
			this->pRight->Copy(tree->RightChild());
		}
	}

	void Thre_ading(InThre_adedTree*& pPre)
	{
		if (this->pLeft != nullptr)
		{
			this->pLeft->Thre_ading(pPre);
		}
		else
		{
			// this->leftTag = PointerType::Thre_ad;
			this->pLeft = pPre;
		}
		if (pPre != nullptr && pPre->pRight == nullptr)
		{
			// pPre->rightTag = PointerType::Thre_ad;
		}
		if (pPre != nullptr && pPre->rightTag == PointerType::Thre_ad)
		{
			pPre->pRight = this;
		}
		pPre = this;
		if (this->pRight != nullptr)
		{
			this->pRight->Thre_ading(pPre);
		}
	}
};


Tree* CreateTree(std::string& str)
{
	Tree* tree = new Tree(str[0]);

	Tree* current = tree;
	int nextSide = 0;
	for (auto i = str.begin() + 1; i != str.end(); ++i)
	{
		if (*i == '#')
		{
			if (nextSide == 0)
			{
				nextSide = 1;
			}
			else
			{
				while (true)
				{
					if (current->Parent() == nullptr)
					{
						return tree;
					}
					if (current->SideOfParent() == Tree::Side::Left)
					{
						current = current->Parent();
						break;
					}
					else
					{
						current = current->Parent();
					}
				}
			}
		}
		else
		{
			if (nextSide == 0)
			{
				current->SetChild(new Tree(*i), Tree::Side::Left);
				current = current->LeftChild();
			}
			else
			{
				current->SetChild(new Tree(*i), Tree::Side::Right);
				current = current->RightChild();
			}
			nextSide = 0;
		}
	}

	return tree;
}


void PrintInOrder(InThre_adedTree* pThre_adedTree)
{
	InThre_adedTree* p = pThre_adedTree;
	while (p != nullptr)
	{
		while (p->LeftTag() == InThre_adedTree::PointerType::Link)
		{
			p = p->Left();
		}
		std::cout << p->Value();
		while (p->RightTag() == InThre_adedTree::PointerType::Thre_ad && p->Right() != nullptr)
		{
			p = p->Right();
			std::cout << p->Value();
		}
		p = p->Right();
	}
}

inline void PrintInfo(InThre_adedTree* p)
{
	auto pSucc = p->Successor();
	if (pSucc != nullptr)
	{
		std::cout << "succ is " << pSucc->Value() << static_cast<int>(pSucc->RightTag()) << std::endl;
	}
	else
	{
		std::cout << "succ is NULL\n";
	}
	auto pPre = p->Precursor();
	if (pPre != nullptr)
	{
		std::cout << "prev is " << pPre->Value() << static_cast<int>(pPre->LeftTag()) << std::endl;
	}
	else
	{
		std::cout << "prev is NULL\n";
	}
}

void FindInOrder(InThre_adedTree* pThre_adedTree, char c)
{
	InThre_adedTree* p = pThre_adedTree;
	bool find = false;
	while (p != nullptr)
	{
		while (p->LeftTag() == InThre_adedTree::PointerType::Link)
		{
			p = p->Left();
		}
		if (p->Value() == c)
		{
			find = true;
			PrintInfo(p);
		}

		while (p->RightTag() == InThre_adedTree::PointerType::Thre_ad && p->Right() != nullptr)
		{
			p = p->Right();
			if (p->Value() == c)
			{
				find = true;
				PrintInfo(p);
			}
		}
		p = p->Right();
	}
	if (!find)
	{
		std::cout << "Not found\n";
	}
}

int main()
{


	std::string line;
	std::cin >> line;
	Tree* tree = CreateTree(line);
	InThre_adedTree* tTree = new InThre_adedTree;
	tTree->CopyTree(*tree);
	char c;
	std::cin >> c;
	PrintInOrder(tTree);
	std::cout << std::endl;
	FindInOrder(tTree, c);



	return 0;
}